package com.xjl.sort;

import com.xjl.utils.SortUtil;

/**
 * @描述： 归并排序，
 *          利用递归思想，代待排序的数组一分为二，分为最小的单元，通过比较大小，排好序后放入一个辅助数组中，
 *          最后将辅助数组的拷贝回原数组。
 *
 * @作者： 许JIAN林
 */
public class MergeSort {

    public static void mergesort(int[] arr, int L, int R) {

        if (arr == null || arr.length<=2){
            return;
        }
        if (L == R) {
            return;
        }

       // int mid = (L + R) / 2;
        int mid = L + ((R - L) >> 1);
        mergesort(arr, L, mid);
        mergesort(arr, mid + 1, R);
        merge(arr, L, mid, R);

    }

    public static void merge(int[] arr, int L, int mid, int R) {

        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = mid+1;

        while (p1 <= mid && p2 <= R){
            help[i++] = arr[p1] < arr[p2]? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while ( p2 <= R) {
            help[i++] = arr[p2++];
        }

        for (int j =0; j<help.length; j++) {
            arr[L+j] = help[j];
        }

    }

    public static void main(String[] args) {
        int [] arr = {45,65,8,47,15,1000};
        mergesort(arr,0, arr.length-1);
        SortUtil.display(arr);

    }


}
